Modern communication systems must cope with varying channel conditions and differing throughput constraints. Polar codes are the first error-correcting codes with an explicit construction to provably achieve the symmetric capacity of memoryless channels unlike currently employed coding such as low-density parity check (LDPC) codes. They have two properties that are of interest to a variety of communications and data transmission/storage systems. First they have a very low error-floor due to their large stopping distance and secondly, low complexity implementations. However, polar codes have two drawbacks: their performance at short to moderate lengths is inferior to that of other codes, such as LDPC codes; and their low-complexity decoding algorithm, successive-cancellation (SC), is serial in nature, leading to low decoding throughput.
Within the prior art multiple methods exist to improve the error-correction performance of polar codes such as using list or list-CRC decoding to improve performance significantly. Alternatively, one can increase the length of the polar code. Among the many throughput-improving methods proposed in literature, simplified successive-cancellation (SSC) and simplified successive-cancellation with maximum-likelihood nodes (ML-SSC) offer the largest improvement over SC decoding. These achieve throughput increases by exploiting the recursive nature of polar codes, where every polar code of length N is formed from two constituent polar codes of length N/2 and decoding the constituent codes directly, without recursion, when possible. SSC decodes constituent codes of rates 0 and 1 directly and ML-SSC additionally enables the direct decoding of smaller constituent codes.
However, it would be beneficial to provide system designers with polar codes, encoders, and decoders that offered even better performance than that within the prior art. Accordingly, it would be beneficial to provide decoders that decode constituent codes without recursion thereby increasing the decoder throughput. Similarly, it would be beneficial for a decoder to recognize classes of constituent codes that can be directly decoded and process these accordingly.
It would be further beneficial to provide designers with encoders and/or decoders that are flexible rather than targeted to a specific polar code. Accordingly, it would be beneficial for such encoders and/or decoders to encode/decode any polar code of any length, n, up to a design maximum, nMAX. Beneficially, such flexibility allows deployed systems to become adaptive to communication link characteristics, performance, etc.
It would also be beneficial to provide designers with flexibility in implementing either hardware or software implementations according to the application such that for example high end data storage solutions may exploit hardware implementations whereas quantum key distribution may exploit software implementations.
It would also be beneficial to enhance discrete elements of prior art decoders as well as advancing new encoders and decoders. Accordingly, the inventors also present enhanced approximation algorithms for improved error correction performance.
Other aspects and features of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures.